package 递归回溯;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-19
 **/

public class No329矩阵中的最长递增路径 {
    /**
     * 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
     * 对于每个单元格，你可以往上，下，左，右四个方向移动。
     * 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
     * <p>
     * 示例 1：
     * 输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
     * 输出：4
     * 解释：最长递增路径为 [1, 2, 6, 9]。
     * 示例 2：
     * 输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
     * 输出：4
     * 解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
     * 示例 3：
     * 输入：matrix = [[1]]
     * 输出：1
     *  
     * 提示：
     * m == matrix.length
     * n == matrix[i].length
     * 1 <= m, n <= 200
     * 0 <= matrix[i][j] <= 2^31 - 1
     */

    /**
     * 高水平代码
     * 如何思考?
     * 1. 将坐标根据其中的值大小进行排序
     * 2. dp初始化为1,代表每格子长度1
     * 3. 从小到大遍历,每次取周围最大的+1即可
     * 4. 因为是从小到大遍历,所以可以保证每次+1都是正确的
     */
    public int longestIncreasingPathGood(int[][] matrix) {

        int allLength = matrix.length;
        int itemLength = matrix[0].length;

        int[][] dp = new int[allLength][itemLength];
        for (int[] ints : dp) {
            Arrays.fill(ints, 1);
        }

        Pair[] arr = new Pair[allLength * itemLength];

        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                int num = matrix[i][j];
                arr[i * itemLength + j] = new Pair(i, j, num);
            }
        }

        Arrays.sort(arr, Comparator.comparingInt(p -> p.num));

        int result = 1;

        for (int i = 0; i < arr.length; i++) {

            Pair pair = arr[i];
            int x = pair.x;
            int y = pair.y;

            for (int j = 0; j < 4; j++) {

                int nextX = x + this.around[j][0];
                int nextY = y + this.around[j][1];

                if (nextX >= 0 && nextX < allLength && nextY >= 0 && nextY < itemLength && matrix[nextX][nextY] < matrix[x][y]) {
                    dp[x][y] = Math.max(dp[x][y], dp[nextX][nextY] + 1);
                    result = Math.max(result, dp[x][y]);
                }

            }

        }

        return result;
    }

    static class Pair {
        private int x;
        private int y;
        private int num;

        public Pair(int x, int y, int num) {
            this.x = x;
            this.y = y;
            this.num = num;
        }
    }

    /**
     * 低水平代码超时了~~
     */
    private int[][] arr;
    private int allLength;
    private int itemLength;
    private int result;
    private int[][] around = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int longestIncreasingPath(int[][] matrix) {
        this.arr = matrix;
        this.allLength = matrix.length;
        this.itemLength = matrix[0].length;

        for (int i = 0; i < this.allLength; i++) {
            for (int j = 0; j < this.itemLength; j++) {
                this.dfs(i, j, 0);
            }
        }

        return this.result + 1;
    }

    private void dfs(int x, int y, int length) {

        this.result = Math.max(this.result, length);

        int num = this.arr[x][y];

        this.arr[x][y] = -1;

        for (int i = 0; i < 4; i++) {

            int nextX = x + this.around[i][0];
            int nextY = y + this.around[i][1];

            if (this.validBorder(nextX, nextY, num)) {
                this.dfs(nextX, nextY, length + 1);
            }

        }

        this.arr[x][y] = num;

    }

    private boolean validBorder(int x, int y, int num) {
        return x >= 0 && x < this.allLength && y >= 0 && y < this.itemLength && this.arr[x][y] != -1 && this.arr[x][y] > num;
    }

    public static void main(String[] args) {
        No329矩阵中的最长递增路径 n = new No329矩阵中的最长递增路径();
        int[][] arr = {{1}, {2}, {3}, {4}};
        int result = n.longestIncreasingPathGood(arr);
        System.out.println(result);
    }

}
